19.7 Stoplessから
Stopless：ロックフリーガベージコレクション
並行な圧縮が行われてる最中でもミューテータの操作がロックフリーであることを保証。
ミューテータがオブジェクトの両方のコピーを更新することはなく、その変わりに"唯一本物のコピーを更新する"。
常に最新のものを更新するということか。
オブジェクトがto空間へとコピーされるまでの間、以下の3つの状態がある。
from空間に通常の状態(ナロー状態)で格納されている。
オブジェクトの各フィールドが「ワイド」である中間状態(そのオブジェクトの移動が開始された状態) ワイドコピーとも言う
ワイドとは、もとのフィールドに加えてステータスフィールドの分だけ広い
ワイドコピーの領域をどこにつくるのかは不明
to空間にコピーされたナロー状態
ナローとは、ステータスフィールドなし
コピーされている途中のオブジェクトのフィールドに、それぞれstatusワードを追加して(「ワイド」状態)、ミューテータにどこを書き換えるかを指示する。
CompareAndSwapWideでこのステータスと、元々のフィールドを同時に書き換える。
ステータスフィールドは以下の値を持つ
inOriginal
ワイドコピーのフィールドが未初期化
from空間の値が最新
inWide
ワイドコピーのフィールドが初期化済み
ワイドコピーの値が最新
inCopy
to空間のナロー状態のフィールドが初期化済み
ミューテータはto空間の値を最新とみなす
このステータスによりミューテータはどこに最新があるかを知る。
最初ワイド状態となったオブジェクトのフィールドは全てinOriginalである。
ステータスワードがinOriginalである時、ミューテータはform空間からreadする。
ミューテータとコレクタはまずどちらもワイドコピーのフィールドに値を順次書き込んでいく。
この時、CASWideを使ってステータスフィールドをinWideにするのと不可分に書き換える。
ミューテータが行うときは、そのミューテータが書き込もうとした値で設定する。
コレクタが行うときは、オリジナルと同じ値で設定する。
inOriginalでないフィールドに対しては、すでにミューテータが変更したということなので、コレクタがすべきことはない。
オブジェクトの全てのフィールドがinWideになったら、コレクタはto空間にナロー状態の領域を用意し、そこのアドレスを転送ポインタとして保持する。
コレクタはワイドコピーからto空間へとフィールドをコピーしていき、CASWで変更が無ければステータスをinCopyに変える。
これがコケたら、ミューテータにより変更されたということなのでやりなおし。
ミューテータはステータスがinCopyだった時は転送ポインタを使ってto空間にあるフィールドを直接触る。
CASWではなくて任意の2ワードを不可分に更新するCAS2が使える場合、ステータスフィールドをオブジェクトのフィールドに隣接しておく必要がないので、ワイドコピーをto空間に作成して、そのままステータスフィールドを除いた部分をナロー状態として利用できそう。
しかし現実にはCAS2がほぼ存在しない
table:表
誰 \ status inOriginal/read inOriginal/write inWide/read inWide/write inCopy
ミューテータ fromから読む CASWでinWideにしつつワイドに書く ワイドから読む (たぶんCAWSでinWideを指定して)ワイドに書く 転送ポインタを使ってtoを読み書き
コレクタ x CASWでinWideにしつつワイドに転送 x toにコピー後CASWでinCopyにする。 表にするの無茶な気がしてきた
空間的オーバーヘッド(ワイド状態だと2倍のサイズな上に、3つもコピーを保持する)を気にするかもしれないけど多分大丈夫みたいなこと。
Staccato：ミューテータがウェイトフリーなベストエフォート圧縮
ロック無し、ミューテータによる不可分操作無し、弱いメモリ順序付けのモデルでも並行圧縮を可能とする。
不可分操作の嵐を避けるために、ほとんどオブジェクトの移動をしない。疎なページを回収する時のみ動かす。動かすオブジェクトをランダムに決定。
全オブジェクトのヘッダに転送ポインタ(以下FP)を持つ。
不揃いな同期
ミューテータが定期的に(GCセーフポイントなどで)メモリフェンスを実施して、「グローバルな状態の更新に関する最新のビューを保つ」(？？)。
転送ポインタの下位1bitはオブジェクトがコピー中であることを示すCOPYING bitとして利用する。
オブジェクトの移動をする時のコレクタの動作は以下のようになる。
1. COPYING bitをCASで立てる。ミューテータはFPを不可分命令を用いずにアクセスするので、しばらくはこの変更をミューテータは気付かない。
2. 「不揃いな同期」で全てのミューテータがリードフェンスを実行するまで待つ。これが終わると↑の変更が全ミューテータに伝搬したことが保証される。
3. if 弱い順序付けのマシン, リードフェンスを実行してミューテータが行なった変更がコレクタに伝播することを保証。
4. コピーを割り付けて、オリジナルから各フィールドをコピー
5. if 弱い順序付けのマシン, ライトフェンスを実行。グローバルに伝播。
6. 「不揃いな同期」で全てのミューテータがリードフェンスを実行するまで待つ。コピーへの変更が全ミューテータへと伝播。
7. 転送アドレスをコピー先として、COPYING bitは落とした状態でCASする。このCASがオブジェクトの移動のcommitである。
もしこれが失敗したということは、ミューテータがコピー中にオブジェクトを更新していたということなので、移動をabortする。
コレクタは複数のオブジェクトを同時に移動しようと試みることで、不揃いな同期のフェンスコストを償却する。
アルゴリズムは以下(アルゴリズム19-8)。copyObjectsは移動すべき候補(candidates)を受けとり、失敗したオブジェクトの一覧(aborted)を返す。
code:アルゴリズム19-8.py
def CompareAndSet(addr, expected, new)
COPYING = 0b1
def CopyObjects(candidates):
replicas = []
aborted = []
for each p in candidates:
CompareAndSet(&p.forwardinAddr(), p, p | COPYING) # 下1bitのCOPYING bitを立てる。
waitForRaggedSynch(readFence) # COPYINGがミューテータに見えるようになるまで待つ
readFence() # CASより前に行われたミューテータの書き込みがコレクタから見えるように
for each p in candidates:
r = alloc(p.size())
copy(r, p) # フィールドをコピー
r.forwardingAddr() = r # コピーのFPは自分自身
replicas << r
writeFence() # ミューテータにコピーを伝播
waitForRaggedSynch(readFence) # 本当にミューテータから見えるように
for each (p in candidates, r in replicas): # for(int i{}, auto p{candidates0}, r{replicas0} ; i < candidates.size(); ++i, p = candidatesi, r = replicasi) ぐらいか。 # コピーのcommitを試みる。
if not CompareAndSet(&p.forwardingAddr(), p | COPYING, r): # 失敗した、つまりミューテータが触った。
free(r) # ここでfreeすると断片化しそうな気がしたが、それは隔離フィット割り付けすれば回避できることだった
aborted << p
return aborted
def Access(p):
r = p.forwardingAddr()
if r & COPYING == 0: # コピー中ではない時はそのまま触っていい。
return r
# コピー中だったので、実行中のコピーをアボートさせようとする。
if CompareAndSet(&p.forwardingAddr(), r, p): # pの転送アドレスの下位1bitを落としたもの(p自身)に戻す。
return p # abortさせることに成功。
# 既にコレクタにcommitされている、もしくは他のミューテータがabortさせた。
atomic:
r = p.forwardingAddr(p) # 最新のforwardingAddrをロードする。ここってなんでread fenceいらないんだろ。atomicだからそういうこともしている？ ↓ に書いてあった。read fenceそのものである。
return r
def Read(p, i):
p2 = Access(p)
def Write(p, i, val):
p2 = Access(p)
ミューテータがアクセスする時は以下の手順となる。
1. 転送ポインタをロード
2. COPYINGでなければそのままアクセスしてよい。
3. そうでない場合、CASでCOPYINGbitを落とそうとする。
4. CASが成功した場合は勝ったので、そのままアクセスできる。
5. そうでない場合、コレクタによるcommitか他のミューテータのabortがあったということを意味するので、FPを不可分に読み出して、その最新の値であることが保証された値の先にアクセスする。
CompareAndSetの変わりにCompareAndSwapを用いればatomic読み出しは消せる(それはそう)。
code:19-9.py
def Access2(p):
r = p.forwardingAddr()
if r & COPYING == 0:
return r
r = CompareAndSwap(&p.forwardingAddr(), r, p)
return r & ~COPYING
CASwapの
成功 → 元のrが返ってくるので、COPYINGを落とせばよい
失敗 → CASwapの定義から最新の値が得られる。COPYINGは立ってないけど、その時r & ~COPYINGではrは不変なのでこのまま使えばよい。
(readでも移動に失敗するので)頻繁にアクセスされるオブジェクトは移動するのは難しい。そういう人気者オブジェクトは、それ自体は移動せずに、そのオブジェクトの乗っているページに他のオブジェクトを移動させてくるのがいいっぽい。
busyなページをto空間にしてしまう作戦
ミューテータのアクセスに時間局所性があるオブジェクト群を移動しようとするとアボートの嵐となる可能性があるが、疎なページの移動を試みる作戦を取っているとそんなことはあまり起こらないことが予想される。
Chicken：ミューテータがウェイトフリーなx86用ベストエフォート型圧縮法
独立に開発されたが、本質的にStaccatoと同じ。
x86-64のメモリモデルでは、CASの後のロードはどのスレッドからも更新後の値が見える
FPを書き換える時にはCASを使ってるので、readのwaitForRaggedSyncがいらなくなって、書き込みでしかabortの必要が無くなる。
不揃いな同期でリードフェンスを実行する必要もない。
code:アルゴリズム19-10.py
def CopyObjects(candidats):
aborted = []
for each p in candidates:
p.forwardingAddr() = p | COPYING
waitForRaggedSynch(readFence) # COPYINGがミューテータに見えるようになるまで待つ
for each p in candidates:
r = alloc(p.size())
copy(p, r)
r.forwardingAddr() = r
if not CompareAndSet(&p.fowardingAddr(), p | COPIYNG, r): # 失敗した。
free(r)
aborted << p
return aborted
def Read(p, i):
r = p.forwardingAddr() & ~COPYING # 本にはないけどCOPYING bitを落とす必要があるのでは。
def Write(p, i, val):
r = p.forwardingAddr()
if r & COPYING != 0: # コピー中だったらそのまま or コピー中なのでabortする。
CompareAndSet(&p.fowardingAddr(), r, r & ~COPYING)
# 成功したならそれでよく、失敗したならコレクタによるcommitか、他のミューテータによるabortがあった。
r = p.forwardingAddr() # ので再度ロード
Clover：圧縮の保証と、確率的なミューテータのロックフリー性
特別な値αを使ってコレクタがフィールドをコピーしている間に、ミューテータがフィールドにアクセスするのを防ぐ
forwardingAddr の設定に関する詳細が抜けているので、細かいところはわからない
αの候補としては、ポインタなら予約されていて使わないような値、浮動小数点数ならNaN(の値のうち普段使わないやつ)
128bitのCompare and Swapとαを用いて衝突の可能性を減らす手法もある
ただし、すべてのRead/Writeが128bit単位になる
code:アルゴリズム19-11.py
alpha = 決して出て来ない値
def CopySlot(p, i):
do:
r = p.forwardingAddr()
while(not CompareAndSwap(&pi, value, alpha)) def Read(p, i):
if val == alpha: # 読みたい値がたまたまalphaとかぶっても動く
r = p.forwadingAddr()
return val
# old == alpha && val != alpha && r == p のケースが怪しい
def Write(p, i, val):
if val == alpha:
コピーが終わるまでスリープ(詳細不明)
do:
if old == alpha:
r = p.forwardingAddr()
break
while(not CompareAndSwap(&pi, old, val)) # srcって書いてあるけど多分p Stopless(ワイドオブジェクト) vs. Chicken(COPYING bit) vs. Clover(alpha)
コレクタの進行性
おそらくロックフリーのこと
Stopless
保証できない
ワイド→コピーの際にミューテータの書き込みがあるとやり直しが発生
Chicken
保証するがアボートする可能性がある
それ、保証するって言うのか?
Clover
保証しているらしい
p496 アルゴリズム19-11の定式化では進行が保証できない
ヒープアクセスの進行性
おさらい
ロックフリー
いずれかのスレッドが有限ステップで処理を終了し、それが無限回繰り返せる
ウェイトフリー
他のスレッドの動きにかかわらず、すべてのスレッドが常に進行可能
Chicken
読み書き両方がウェイトフリー
p496上のコードから明らか
CloverとStopless
読み込みはウェイトフリー
書き込みはロックフリー
Cloverでミューテータが値αを書き込む場合はロック
CompareAndSwapでぐるぐる回るケースはどうなのか?
分割割付
トレードオフなしにはリアルタイムGCで断片化除去は難しい
Chiecken, Staccato
コピーのアボート
Stopless, Clover
ヒープアクセスがウェイトフリーでない
オブジェクト/配列を固定サイズのob-let(オブレット)に分割することで断片化を抑える by Siebert
断片化除去ではなくて、はじめから断片化させない戦略
オブジェクト
オブジェクトをオブレットのリストで表現する
オブジェクトの後ろのフィールドアクセスにフィールド番号に比例する時間がかかる
配列
配列は二分木で持つ
配列要素のアクセスには配列サイズの対数時間かかる
一般に配列のサイズは事前にわからない
最悪実行時間の上界が定まらない
オブジェクト/配列を固定サイズのob-let(オブレット)に分割することで断片化を抑える by Pizlo
Schism
図を見て
背骨は可変長であり、断片化する
https://gyazo.com/041e4338ec4c9ec6d61b2b62a81b162e
新規性
背骨はオブジェクト/配列空間に割り付ける必要がない
背骨は書き換え不可でミューテータによる更新がない
配列の断片を管理する新たな断片(背骨)を配列の一部としてメモリ上に確保する必要がない
配列の背骨は別に管理する空間に保存しレプリケーションGCする
背骨はアレイレットへのポインタのみを含んでおり、アレイレットは移動しないので、レプリケーションGCによる移動で壊れる可能性はない
ここの背骨は番兵からのポインタでアクセスされる
レプリケーションGCでコピーするときは、番兵から背骨へのポインタをミューテータとの同期なしに切り替えることができる
背骨の内容が変わらないので
利点
ヒープへのアクセスがウェイトフリー
断片化しにくい
配列を連続に配置することで高速化もできる
連続に配置できない場合のアクセスコストが上昇するデメリットがある
連続に配置できた/できないのif文が遅い?
連続に配置したときに比べて相対的に上昇するということか?
アクセスコストが常に予想可能でなければならない場合は常に分割して割り付けるようにすれば良い
コスト: 配列アクセスにかならず背骨の間接参照コストが挟まる
利点: 最大停止時間が改善
連続的に割り付けられる配置を探すのに時間がかかる